//1. 有效的括号  题目链接：https://leetcode.cn/problems/valid-parentheses/description/
class Solution {
public:
    bool isValid(string s) {
         map<char, char> mp({make_pair('(',')'), make_pair('[',']'), make_pair('{','}')});
         stack<char> st;
         //左括号入栈，右括号出栈比较
         for (auto& e : s)
         {
            if (mp.find(e) != mp.end()) {st.push(e);}
            else
            {
                if (!st.empty())
                {
                    char c = st.top();
                    st.pop();
                    if (e != mp[c]) {return false;}
                }
                else {return false;}
            }
         }
         if (st.empty()) {return true;}
         else {return false;}
    }
};

//2. 最小覆盖子串 【2024-滴滴-开发、2023-腾讯天美-开发】题目链接：https://leetcode.cn/problems/minimum-window-substring/description/

class Solution {
public:
    bool Check(map<char, int>& mp1, map<char, int>& mp2)
    {
        //检查是否已经满足覆盖条件
        if (mp1.size() == mp2.size())
        {
            for (auto& e : mp2)
            {
                if (e.second < mp1[e.first]) { return false; }
            }
            return true;
        }
        return false;
    }

    string minWindow(string s, string t) {
        string ans;
        if (s.size() < t.size()) {return ans;}
        
        //记录t中的值
        map<char, int> mp1;
        for (auto& e : t) { mp1[e]++; }

        //滑动窗口，字符串s
        map<char, int> mp2;
        int n = s.size();
        int left = 0, right = 0;
        int min_size = 100000;
        for (; left < n; ++left)
        {
            //left右移
            if (left != 0)
            {
                if (mp2.find(s[left - 1]) != mp2.end() && --mp2[s[left - 1]] == 0)
                {
                    //减到0就删了
                    mp2.erase(s[left - 1]);
                }
                //跳过无关字符
                while (left < n && mp1.find(s[left]) == mp1.end()) { ++left; }
            }
            //right右移
            while (right < n && !Check(mp1, mp2))
            {
                if (mp1.find(s[right]) != mp1.end()) { mp2[s[right]]++; }
                ++right;
            }
            //最小字符串筛选
            if (right < n || Check(mp1, mp2))
            {
                int tmp = right - left;
                if (tmp < min_size)
                {
                    min_size = tmp;
                    ans.resize(min_size);
                    memcpy((char*)ans.c_str(), s.c_str() + left, min_size);
                }
            }
        }
        return ans;
    }
};
